package com.zhangxin.ch1;

/**
 * 1 2 3 3 3 4 5
 * 两种划分方式
 * 1)一部分 x<=3  ,一部分是x > 3
 * 2)一部分 x <3 ,一部分是 x >=3
 */
public class BinarySearch {
    public static void main(String[] args) {
        int[] arr = {1, 2, 3, 3, 3, 4, 5};
        int start = binarySearch1(arr, 0, arr.length - 1, 3);
        System.out.println(start);
        int end = binarySearch2(arr, 0, arr.length - 1, 3);
        System.out.println(end);
    }

    // 返回 数组中 第一个 大于等于 x 的下标,没找到返回-1
    private static int binarySearch1(int[] arr, int left, int right, int x) {
        while (left < right) {
            int mid = left + right >> 1;
            if (arr[mid] >= x) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        if (arr[left] != x) {
            return -1;
        }
        return left;
    }

    // 返回 数组中 最后一个 小于等于 x 的下标，没找到返回-1
    private static int binarySearch2(int[] arr, int left, int right, int x) {
        while (left < right) {
            int mid = left + right + 1 >> 1;
            if (arr[mid] <= x) {
                left = mid;
            } else {
                right = mid - 1;
            }
        }
        if (arr[left] != x) {
            return -1;
        }
        return left;
    }


}
